package com.example.bst;

/**
 * 二叉树的递归套路
 * 可解决面试中绝大多数的二叉树问题 尤其是树型dp问题
 * 本职是利用递归遍历二叉树的便利性
 * <br/>
 * 1) 假设以X节点为头，假设可以向X左数和X右数要任何信息
 * 2) 在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
 * 3) 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
 * 4) 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
 * 5) 递归函数都返回S，每一颗子树都这么要求
 * 6) 写代码，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息
 *
 * @Date 2022/4/6
 * @Created by Jonathan
 */

public class BalanceBST {

    static class Node {
        Integer value;
        Node right;
        Node left;
    }

    static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    // 给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡树
    public Info process(Node x) {
        // base case
        if (x == null)
            return new Info(true, 0);
        Info left = process(x.left);
        Info right = process(x.right);

        // 左右最大的加一
        int height = Math.max(left.height, right.height) + 1;
        boolean isBalanced = true;
        // 左边不是 || 右边不是 || 左右的高度差超过1
        if (!left.isBalanced || !right.isBalanced || Math.abs(left.height) - right.height > 1) {
            isBalanced = false;
        }
        return new Info(isBalanced, height);
    }


}
